home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 3 / Amiga Tools 3.iso / grafik / raytracing / rayshade-4.0.6.3 / libray / libobj / grid.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-09  |  11.7 KB  |  506 lines
  1. /*
  2.  * grid.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * grid.c,v 4.1 1994/08/09 07:59:07 explorer Exp
  17.  *
  18.  * grid.c,v
  19.  * Revision 4.1  1994/08/09  07:59:07  explorer
  20.  * Bump version to 4.1
  21.  *
  22.  * Revision 1.1.1.1  1994/08/08  04:52:09  explorer
  23.  * Initial import.  This is a prerelease of 4.0.6enh3, or 4.1 possibly.
  24.  *
  25.  * Revision 4.0.1.1  91/10/04  15:55:37  cek
  26.  * patch1: Removed straight floating point comparisons.
  27.  * 
  28.  * Revision 4.0  91/07/17  14:38:02  kolb
  29.  * Initial version.
  30.  * 
  31.  */
  32. #include "geom.h"
  33. #include "grid.h"
  34.  
  35. static Methods *iGridMethods = NULL;
  36. static char gridName[] = "grid";
  37.  
  38. static unsigned long raynumber = 1;        /* Current "ray number". */
  39.                         /* (should be "grid number") */
  40. static void engrid(), GridFreeVoxels();
  41. static int pos2grid(), CheckVoxel();
  42.  
  43. Grid *
  44. GridCreate(x, y, z)
  45. int x, y, z;
  46. {
  47.     Grid *grid;
  48.  
  49.     if (x < 1 || y < 1 || z < 1) {
  50.         RLerror(RL_WARN, "Invalid grid specification.\n");
  51.         return (Grid *)NULL;
  52.     }
  53.     grid = (Grid *)share_calloc(1, sizeof(Grid));
  54.     grid->xsize = x;
  55.     grid->ysize = y;
  56.     grid->zsize = z;
  57.     return grid;    
  58. }
  59.  
  60. char *
  61. GridName()
  62. {
  63.     return gridName;
  64. }
  65.  
  66. /*
  67.  * Intersect ray with grid, returning distance from "pos" to
  68.  * nearest intersection with an object in the grid.  Returns 0.
  69.  * if no intersection.
  70.  */
  71. int
  72. GridIntersect(grid, ray, hitlist, mindist, maxdist)
  73. Grid *grid;
  74. Ray *ray;
  75. HitList *hitlist;
  76. Float mindist, *maxdist;
  77. {
  78.     GeomList *list;
  79.     Geom *obj;
  80.     int hit;
  81.     Float offset, tMaxX, tMaxY, tMaxZ;
  82.     Float tDeltaX, tDeltaY, tDeltaZ, *raybounds[2][3];
  83.     int stepX, stepY, stepZ, outX, outY, outZ, x, y, z;
  84.     Vector curpos, nXp, nYp, nZp, np, pDeltaX, pDeltaY, pDeltaZ;
  85.     unsigned long counter;
  86.  
  87.     hit = FALSE;
  88.     /*
  89.      * Check unbounded objects.
  90.      */
  91.     for (obj = grid->unbounded ; obj; obj = obj->next) {
  92.         if (intersect(obj, ray, hitlist, mindist, maxdist))
  93.             hit = TRUE;
  94.     }
  95.  
  96.     /*
  97.      * If outside of the bounding box, check to see if we
  98.      * hit it.
  99.      */
  100.     VecAddScaled(ray->pos, mindist, ray->dir, &curpos);
  101.     if (OutOfBounds(&curpos, grid->bounds)) {
  102.         offset = *maxdist;
  103.         if (!BoundsIntersect(ray, grid->bounds, mindist, &offset))
  104.             /*
  105.              * Ray never hit grid space.
  106.              */
  107.             return hit;
  108.         /*
  109.          * else
  110.          *    The ray enters voxel space before it hits
  111.          *     an unbounded object.
  112.          */
  113.         VecAddScaled(ray->pos, offset, ray->dir, &curpos);
  114.     } else
  115.         offset = mindist;
  116.  
  117.     counter = raynumber++;
  118.  
  119.     /*
  120.      * tMaxX is the absolute distance from the ray origin we must move
  121.      *        to get to the next voxel in the X
  122.      *        direction.  It is incrementally updated
  123.      *         by DDA as we move from voxel-to-voxel.
  124.      * tDeltaX is the relative amount along the ray we move to
  125.      *        get to the next voxel in the X direction. Thus,
  126.      *        when we decide to move in the X direction,
  127.      *         we increment tMaxX by tDeltaX.
  128.      */
  129.     x = x2voxel(grid, curpos.x);
  130.     if (x == grid->xsize)
  131.         x--;
  132.     if (fabs(ray->dir.x) < EPSILON) {
  133.         tMaxX = FAR_AWAY;
  134.         raybounds[LOW][X] = &curpos.x;
  135.         raybounds[HIGH][X] = &np.x;
  136.         tDeltaX = 0.;
  137.     } else if (ray->dir.x < 0.) {
  138.         tMaxX = offset + (voxel2x(grid, x) - curpos.x) / ray->dir.x;
  139.         tDeltaX = grid->voxsize[X] / - ray->dir.x;
  140.         stepX = outX = -1;
  141.         raybounds[LOW][X] = &np.x;
  142.         raybounds[HIGH][X] = &curpos.x;
  143.     } else {
  144.         tMaxX = offset + (voxel2x(grid, x+1) - curpos.x) / ray->dir.x;
  145.         tDeltaX = grid->voxsize[X] / ray->dir.x;
  146.         stepX = 1;
  147.         outX = grid->xsize;
  148.         raybounds[LOW][X] = &curpos.x;
  149.         raybounds[HIGH][X] = &np.x;
  150.     }
  151.  
  152.     y = y2voxel(grid, curpos.y);
  153.     if (y == grid->ysize)
  154.         y--;
  155.  
  156.     if (fabs(ray->dir.y) < EPSILON) {
  157.         tMaxY = FAR_AWAY;
  158.         raybounds[LOW][Y] = &curpos.y;
  159.         raybounds[HIGH][Y] = &np.y;
  160.         tDeltaY = 0.;
  161.     } else if (ray->dir.y < 0.) {
  162.         tMaxY = offset + (voxel2y(grid, y) - curpos.y) / ray->dir.y;
  163.         tDeltaY = grid->voxsize[Y] / - ray->dir.y;
  164.         stepY = outY = -1;
  165.         raybounds[LOW][Y] = &np.y;
  166.         raybounds[HIGH][Y] = &curpos.y;
  167.     } else {
  168.         tMaxY = offset + (voxel2y(grid, y+1) - curpos.y) / ray->dir.y;
  169.         tDeltaY = grid->voxsize[Y] / ray->dir.y;
  170.         stepY = 1;
  171.         outY = grid->ysize;
  172.         raybounds[LOW][Y] = &curpos.y;
  173.         raybounds[HIGH][Y] = &np.y;
  174.     }
  175.  
  176.     z = z2voxel(grid, curpos.z);
  177.     if (z == grid->zsize)
  178.         z--;
  179.     if (fabs(ray->dir.z) < EPSILON) {
  180.         tMaxZ = FAR_AWAY;
  181.         raybounds[LOW][Z] = &curpos.z;
  182.         raybounds[HIGH][Z] = &np.z;
  183.         tDeltaZ = 0.;
  184.     } else if (ray->dir.z < 0.) {
  185.         tMaxZ = offset + (voxel2z(grid, z) - curpos.z) / ray->dir.z;
  186.         tDeltaZ = grid->voxsize[Z] / - ray->dir.z;
  187.         stepZ = outZ = -1;
  188.         raybounds[LOW][Z] = &np.z;
  189.         raybounds[HIGH][Z] = &curpos.z;
  190.     } else {
  191.         tMaxZ = offset + (voxel2z(grid, z+1) - curpos.z) / ray->dir.z;
  192.         tDeltaZ = grid->voxsize[Z] / ray->dir.z;
  193.         stepZ = 1;
  194.         outZ = grid->zsize;
  195.         raybounds[LOW][Z] = &curpos.z;
  196.         raybounds[HIGH][Z] = &np.z;
  197.     }
  198.  
  199.     VecScale(tDeltaX, ray->dir, &pDeltaX);
  200.     VecScale(tDeltaY, ray->dir, &pDeltaY);
  201.     VecScale(tDeltaZ, ray->dir, &pDeltaZ);
  202.  
  203.     VecAddScaled(ray->pos, tMaxX, ray->dir, &nXp);
  204.     VecAddScaled(ray->pos, tMaxY, ray->dir, &nYp);
  205.     VecAddScaled(ray->pos, tMaxZ, ray->dir, &nZp);
  206.  
  207.     while (TRUE) {
  208.         list = grid->cells[x][y][z];
  209.         if (tMaxX < tMaxY && tMaxX < tMaxZ) {
  210.             if (list) {
  211.                 np = nXp;
  212.                     if (CheckVoxel(list,ray,raybounds,
  213.                         hitlist,counter,mindist,maxdist))
  214.                     hit = TRUE;
  215.             }
  216.             x += stepX;
  217.             if (*maxdist < tMaxX || x == outX)
  218.                 break;
  219.             tMaxX += tDeltaX;
  220.             curpos = nXp;
  221.             nXp.x += pDeltaX.x;
  222.             nXp.y += pDeltaX.y;
  223.             nXp.z += pDeltaX.z;
  224.         } else if (tMaxZ < tMaxY) {
  225.             if (list) {
  226.                 np = nZp;
  227.                     if (CheckVoxel(list,ray, raybounds,
  228.                         hitlist,counter,mindist,maxdist))
  229.                     hit = TRUE;
  230.             }
  231.             z += stepZ;
  232.             if (*maxdist < tMaxZ || z == outZ)
  233.                 break;
  234.             tMaxZ += tDeltaZ;
  235.             curpos = nZp;
  236.             nZp.x += pDeltaZ.x;
  237.             nZp.y += pDeltaZ.y;
  238.             nZp.z += pDeltaZ.z;
  239.         } else {
  240.             if (list) {
  241.                 np = nYp;
  242.                     if (CheckVoxel(list,ray,raybounds,
  243.                         hitlist,counter,mindist,maxdist))
  244.                     hit = TRUE;
  245.             }
  246.             y += stepY;
  247.             if (*maxdist < tMaxY || y == outY)
  248.                 break;
  249.             tMaxY += tDeltaY;
  250.             curpos = nYp;
  251.             nYp.x += pDeltaY.x;
  252.             nYp.y += pDeltaY.y;
  253.             nYp.z += pDeltaY.z;
  254.         }
  255.     }
  256.     return hit;
  257. }
  258.  
  259. /*
  260.  * Intersect ray with objects in grid cell.  Note that there are a many ways
  261.  * to speed up this routine, all of which uglify the code to a large extent.
  262.  */
  263. static int
  264. CheckVoxel(list,ray,raybounds,hitlist,counter,mindist,maxdist)
  265. GeomList *list;
  266. Ray *ray;
  267. Float *raybounds[2][3];
  268. HitList *hitlist;
  269. unsigned long counter;
  270. Float mindist, *maxdist;
  271. {
  272.     Geom *obj;
  273.     int hit;
  274.     Float lx, hx, ly, hy, lz, hz;
  275.  
  276.     lx = *raybounds[LOW][X];
  277.     hx = *raybounds[HIGH][X];
  278.     ly = *raybounds[LOW][Y];
  279.     hy = *raybounds[HIGH][Y];
  280.     lz = *raybounds[LOW][Z];
  281.     hz = *raybounds[HIGH][Z];
  282.  
  283.     hit = FALSE;
  284.  
  285.     do {
  286.         obj = list->obj;
  287.         /*
  288.          * If object's counter is greater than or equal to the
  289.          * number associated with the current grid,
  290.          * don't bother checking again.  In addition, if the
  291.          * bounding box of the ray's extent in the voxel does
  292.          * not intersect the bounding box of the object, don't bother.
  293.          */
  294. #ifdef SHAREDMEM
  295.         if (*obj->counter < counter &&
  296. #else
  297.         if (obj->counter < counter &&
  298. #endif
  299.             obj->bounds[LOW][X] <= hx  &&
  300.             obj->bounds[HIGH][X] >= lx &&
  301.             obj->bounds[LOW][Y] <= hy  &&
  302.             obj->bounds[HIGH][Y] >= ly &&
  303.             obj->bounds[LOW][Z] <= hz  &&
  304.             obj->bounds[HIGH][Z] >= lz) {
  305. #ifdef SHAREDMEM
  306.             *obj->counter = counter;
  307. #else
  308.             obj->counter = counter;
  309. #endif
  310.             if (intersect(obj, ray, hitlist, mindist, maxdist))
  311.                 hit = TRUE;
  312.         }
  313.     } while ((list = list->next) != (GeomList *)0);
  314.  
  315.     return hit;
  316. }
  317.  
  318. int
  319. GridConvert(grid, objlist)
  320. Grid *grid;
  321. Geom *objlist;
  322. {
  323.     int num;
  324.  
  325.     /*
  326.      * Keep linked list of all bounded objects in grid; it may come
  327.      * in handy.
  328.      */
  329.     grid->objects = objlist;
  330.     for (num = 0; objlist; objlist = objlist->next)
  331.         num += objlist->prims;
  332.  
  333.     return num;
  334. }
  335.  
  336. void
  337. GridBounds(grid, bounds)
  338. Grid *grid;
  339. Float bounds[2][3];
  340. {
  341.     Geom *obj, *ltmp;
  342.     int x, y, i;
  343.  
  344.     BoundsInit(bounds);
  345.     /*
  346.      * For each object on the list,
  347.      * compute its bounds...
  348.      */
  349.     /*
  350.      * Find bounding box of bounded objects and get list of
  351.      * unbounded objects.
  352.      */
  353.     grid->unbounded = GeomComputeAggregateBounds(&grid->objects,
  354.                 grid->unbounded, grid->bounds);
  355.  
  356.     BoundsCopy(grid->bounds, bounds);
  357.  
  358.     grid->voxsize[X] = (grid->bounds[HIGH][X]-grid->bounds[LOW][X])/
  359.                 grid->xsize;
  360.     grid->voxsize[Y] = (grid->bounds[HIGH][Y]-grid->bounds[LOW][Y])/
  361.                 grid->ysize;
  362.     grid->voxsize[Z] = (grid->bounds[HIGH][Z]-grid->bounds[LOW][Z])/
  363.                 grid->zsize;
  364.  
  365.     if (grid->cells == (GeomList ****)NULL) {
  366.         /*
  367.           * Allocate voxels.
  368.           */
  369.         grid->cells = (GeomList ****)share_malloc(grid->xsize *
  370.                     sizeof(GeomList ***));
  371.         for (x = 0; x < grid->xsize; x++) {
  372.             grid->cells[x] = (GeomList ***)share_malloc(grid->ysize *
  373.                 sizeof(GeomList **));
  374.             for (y = 0; y < grid->ysize; y++)
  375.                 grid->cells[x][y] = (GeomList **)share_calloc(
  376.                     (unsigned)grid->zsize,sizeof(GeomList *));
  377.         }
  378.     } else {
  379.         /*
  380.          * New frame...
  381.          * Free up the objlists in each voxel.
  382.          */
  383.         GridFreeVoxels(grid);
  384.     }
  385.  
  386.     /*
  387.      * objlist now holds a linked list of bounded objects.
  388.      */
  389.     for (ltmp = grid->objects; ltmp != (Geom *)0; ltmp = ltmp->next)
  390.         engrid(ltmp, grid);
  391. }
  392.  
  393. static void
  394. GridFreeVoxels(grid)
  395. Grid *grid;
  396. {
  397.     int x, y, z;
  398.     GeomList *cell, *next;
  399.  
  400.     for (x = 0; x < grid->xsize; x++) {
  401.         for (y = 0; y < grid->ysize; y++) {
  402.             for (z = 0; z < grid->zsize; z++) {
  403.                 for (cell = grid->cells[x][y][z]; cell; cell = next) {
  404.                     next = cell->next;
  405.                     free((voidstar)cell);
  406.                 }
  407.                 grid->cells[x][y][z] = (GeomList *)NULL;
  408.             }
  409.         }
  410.     }
  411. }
  412.  
  413. Methods *
  414. GridMethods()
  415. {
  416.     if (iGridMethods == (Methods *)NULL) {
  417.         iGridMethods = MethodsCreate();
  418.         iGridMethods->methods = GridMethods;
  419.         iGridMethods->create = (GeomCreateFunc *)GridCreate;
  420.         iGridMethods->intersect = GridIntersect;
  421.         iGridMethods->name = GridName;
  422.         iGridMethods->convert = GridConvert;
  423.         iGridMethods->bounds = GridBounds;
  424.         iGridMethods->checkbounds = FALSE;
  425.         iGridMethods->closed = TRUE;
  426.     }
  427.     return iGridMethods;
  428. }
  429.  
  430. /*
  431.  * Place an object in a grid.
  432.  */
  433. static void
  434. engrid(obj, grid)
  435. Geom *obj;
  436. Grid *grid;
  437. {
  438.     int x, y, z, low[3], high[3];
  439.     GeomList *ltmp;
  440.  
  441.     /*
  442.      * This routine should *never* be passed an unbounded object, but...
  443.      */
  444.     if (!pos2grid(grid, obj->bounds[LOW], low) ||
  445.         !pos2grid(grid, obj->bounds[HIGH], high) ||
  446.         obj->bounds[LOW][X] > obj->bounds[HIGH][X]) {
  447.         /*
  448.          * Geom is partially on wholly outside of
  449.          * grid -- this should never happen, but just
  450.          * in case...
  451.          */
  452.         RLerror(RL_ABORT, "Engrid got an unbounded object?!\n");
  453.         return;
  454.         }
  455.  
  456.     /*
  457.      * For each voxel that intersects the object's bounding
  458.      * box, add pointer to this object to voxel's linked list.
  459.       */
  460.     for (x = low[X]; x <= high[X]; x++) {
  461.         for (y = low[Y]; y <= high[Y]; y++) {
  462.             for (z = low[Z]; z <= high[Z]; z++) {
  463.                 ltmp = (GeomList *)share_malloc(sizeof(GeomList));
  464.                 ltmp->obj = obj;
  465.                 ltmp->next = grid->cells[x][y][z];
  466.                 grid->cells[x][y][z] = ltmp;
  467.             }
  468.         }
  469.     }
  470. }
  471.  
  472. /*
  473.  * Convert 3D point to index into grid's voxels.
  474.  */
  475. static int
  476. pos2grid(grid, pos, index)
  477. Grid *grid;
  478. Float pos[3];
  479. int index[3];
  480. {
  481.     index[X] = (int)(x2voxel(grid, pos[0]));
  482.     index[Y] = (int)(y2voxel(grid, pos[1]));
  483.     index[Z] = (int)(z2voxel(grid, pos[2]));
  484.  
  485.     if (index[X] == grid->xsize)
  486.         index[X]--;
  487.     if (index[Y] == grid->ysize)
  488.         index[Y]--;
  489.     if (index[Z] == grid->zsize)
  490.         index[Z]--;
  491.  
  492.     if (index[X] < 0 || index[X] >= grid->xsize ||
  493.         index[Y] < 0 || index[Y] >= grid->ysize ||
  494.         index[Z] < 0 || index[Z] >= grid->zsize)
  495.         return FALSE;
  496.     return TRUE;
  497. }
  498.  
  499. void
  500. GridMethodRegister(meth)
  501. UserMethodType meth;
  502. {
  503.     if (iGridMethods)
  504.         iGridMethods->user = meth;
  505. }
  506.